// 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

// 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

// 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。



//被骂的写法
// function findKthLargest(nums: number[], k: number): number {
//     nums.sort((a,b)=> b-a)
//     return nums[k-1]
// };



//因为要取出第k个的最大元素，可以先设置一个可以放k个元素的数组，然后比对原数组，把k个最大的值放入这数组中，然后这个数组的最小值就是原数组中第k个最大的元素


//但是这种方法超出限制拉
// function findKthLargest(nums: number[], k: number): number {
//     let Klist:number[] = []
//     for(let i = 0; i<nums.length;i++){
//         if(Klist.length < k){
//             Klist.push(nums[i])
//         }else{
//             let min = Math.min(...Klist)
//             if(min < nums[i]){
//                 Klist[Klist.indexOf(min)] = nums[i]
//             }
//         }
//     }
   
//     return Math.min(...Klist)
// };


//解释的过程
// https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/836425/xie-gei-qian-duan-tong-xue-de-ti-jie-yi-kt5p2
//大顶堆
function findKthLargest(nums: number[], k: number): number {
   let numslenght = nums.length
   createMaxHeap(nums,numslenght)
   for(let i = nums.length - 1;i>=nums.length - k + 1 ;i--){
    console.log(i)
    swap(nums,0,i)
    --numslenght
    sortMaxHeap(nums,0,numslenght)
   }
   return(nums[0])
   //创建大顶堆
   function createMaxHeap(arr:number[],length:number){
    for(let i = Math.floor(length/2) - 1;i>=0;i--){
        sortMaxHeap(arr,i,length)
    }
   }
   
   //对堆进行排序
   function sortMaxHeap(arr:number[],i:number,length:number){
    let l = i*2 + 1
    let r = i*2 + 2
    let maxi = i
    if(l < length && arr[l] > arr[maxi]){
        maxi = l
    }
    if(r < length && arr[r] > arr[maxi]){
        maxi = r
    }
    if(maxi != i){
        swap(nums,maxi,i)
        sortMaxHeap(nums,maxi,length)
    }

   }
   //交换位置
   function swap(arr:number[],pre:number,nex:number){
    let temp = arr[pre]
    arr[pre] = arr[nex]
    arr[nex] = temp
   }
};

console.log(findKthLargest([3,2,3,1,2,4,5,5,6],2))